package com.hgc.ch02.sort;

import com.hgc.ch02.tool.MakeArray;

import java.util.Arrays;

/**
 * Created by 01367627 on 2019/7/5.
 */
public class SortUtil {

    /**
     * 冒泡
     *
     * @param array
     * @return
     */
    public static int[] bubbleSort(int[] array) {
        if (array.length == 0) {
            return array;
        }
        int temp;
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (array[i] < array[j]) {
                    temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
        }
        return array;
    }

    public static int[] quickSort(int[] array, int start, int end) {
        if (array.length == 0 || start >= end) {
            return array;
        }
        int left = start;
        int right = end;
        int pivot = array[left];
        while (left < right) {
            while (left < right && array[right] >= pivot) {
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] <= pivot) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = pivot;
        quickSort(array, start, left - 1);
        quickSort(array, left + 1, end);
        return array;
    }

    /**
     * 插入
     *
     * @param array
     * @return
     */
    public static int[] insertionSort(int[] array) {
        if (array.length == 0) {
            return array;
        }
        int currentValue;
        for (int i = 0; i < array.length - 1; i++) {
            int preIndex = i;
            currentValue = array[preIndex + 1];
            while (preIndex >= 0 && currentValue < array[preIndex]) {
                array[preIndex + 1] = array[preIndex];
                preIndex--;
            }
            array[preIndex + 1] = currentValue;
        }
        return array;
    }

    /**
     * 归并
     *
     * @param array
     * @return
     */
    public static int[] mergeSort(int[] array) {
        if (array.length < MakeArray.THRESHOLD) {
            return insertionSort(array);
        }
        int middle = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, middle);
        int[] right = Arrays.copyOfRange(array, middle, array.length);
        return merge(mergeSort(left), mergeSort(right));
    }

    public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            if (i >= left.length)/*左边数组已经取完，完全取右边数组的值即可*/
                result[index] = right[j++];
            else if (j >= right.length)/*右边数组已经取完，完全取左边数组的值即可*/
                result[index] = left[i++];
            else if (left[i] > right[j])/*左边数组的元素值大于右边数组，取右边数组的值*/
                result[index] = right[j++];
            else/*右边数组的元素值大于左边数组，取左边数组的值*/
                result[index] = left[i++];
        }
        return result;
    }

    public static void print(int[] array) {
        int cnt = 0;
        for (int i = 0; i < array.length; i++) {
            if (cnt < 50) {
                System.out.print(array[i] + " ");
                cnt++;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = MakeArray.makeArray(20);
        //int[] array = new int[]{5, 3, 9, 7, 1};
        long start = System.currentTimeMillis();
        array = quickSort(array, 0, array.length - 1);
        //array = insertionSort(array);
        //array = mergeSort(array);
        System.out.println("排序花费：" + (System.currentTimeMillis() - start) + "ms");
        print(array);
    }

}
